/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.checks;

import java.util.BitSet;
import java.util.Random;

import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.FinalHintProducer;
import com.onegravity.sudoku.solver.core.Hint;
import com.onegravity.sudoku.solver.core.WarningHintProducer;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.NeighborManager;

/**
 * This producer solves a puzzle and might produce one of the following hints (one and only one):
 *  
 * - SolutionHint: puzzle successfully solved
 * - NoSolutionHint: no solution found
 * - MultipleSolutionsHint: multiple solutions found
 * 
 * @author Emanuel Moecklin
 */
public class SolutionProducer implements WarningHintProducer, FinalHintProducer {

	private static final boolean OUTPUT = false; 
	
    private boolean returnSolution;
    
    private int maxNrOfIterations;
    private int nrOfIterations;
    private int nrOfSolutions;
    
    private Grid theUnsolvedGrid;
    private Grid theSolvedGrid;
    
    // defines how many solutions the solver will find before it stops
    private int maxNrOfSolutions;

    /**
     * The constructor
     * @param returnSolution if True a SolutionHint will be produced in case the puzzle has exactly one solution,
     * if False no such hint will ever be produced (but NoSolution and MultipleSolutions)
     */
    public SolutionProducer(boolean returnSolution) {
    	this.returnSolution = returnSolution;
    }

    /**
     * Get hints that can be found from a brute-force analysis.
     * <p>
     * A warning/information hint is produced in one of the following case:
     * <ul>
     * <li>If the sudoku has no solution
     * <li>If the sudoku has more than one solution. The produced hint
     * contains two different solutions
     * <li>If the sudoku has exactly one solution, and <tt>true</tt> was passed
     * for <tt>includeSoluton</tt> in the constructor, a hint with the solution
     * is produced.
     * </ul>
     */
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException  {
    	long l = System.currentTimeMillis();
    	maxNrOfSolutions = 2;
    	maxNrOfIterations = Integer.MAX_VALUE;
    	nrOfIterations = 0;
    	nrOfSolutions = 0;
    	theUnsolvedGrid = grid;
    	theSolvedGrid = null;

    	SolverGrid solverGrid = new SolverGrid(grid);
    	solve(solverGrid, new Random());

    	Hint hint = null;
    	switch (nrOfSolutions) {
    	case 0:
			 hint = new NoSolutionHint(grid);
			 break;
    	case 1:
            hint = returnSolution ? new SolutionHint(grid, theSolvedGrid) : null;
            break;
   		default:
			 hint = new MultipleSolutionsHint(grid);
    	}
    	if (OUTPUT) System.out.println("getHints() took " + (System.currentTimeMillis()-l)/1000f + " seconds"); //$NON-NLS-1$ //$NON-NLS-2$
    	if (OUTPUT) System.out.println("nrOfIterations: " + nrOfIterations); //$NON-NLS-1$

        if (hint!=null) accu.add(hint);
    }

    public boolean solve(Grid grid, Random rand, int maxNrOfIterations) throws InterruptedException {
    	long l = System.currentTimeMillis();
    	
    	this.maxNrOfIterations = maxNrOfIterations;
    	grid.rebuildPotentialValues();
    	SolverGrid solverGrid;
    	do {
        	maxNrOfSolutions = 1;
        	nrOfIterations = 0;
        	nrOfSolutions = 0;
        	theUnsolvedGrid = grid;
        	theSolvedGrid = null;
        	solverGrid = new SolverGrid(grid);
        } while (!solve(solverGrid, rand));
    	
    	if (OUTPUT) System.out.println("solve(Grid) took " + (System.currentTimeMillis()-l)/1000f + " seconds"); //$NON-NLS-1$ //$NON-NLS-2$
    	if (OUTPUT) System.out.println("nrOfIterations: " + nrOfIterations); //$NON-NLS-1$

    	if (nrOfSolutions==1) {
            Hint hint = new SolutionHint(grid, theSolvedGrid);
    		hint.apply();
    		return true;
    	}
    	
		return false;
    }
    
    /**
     * Get information about the number of solutions of the given
     * sudoku grid.
     * <p>
     * The following values can be returned:
     * <ul>
     * <li><b>0</b> if the sudoku has no solution
     * <li><b>1</b> if the sudoku has exactly one solution
     * <li><b>2</b> if the sudoku has <i>more than one</i> solution
     * </ul>
     * <p>
     * Warning: you should first check that no value appear twice in the
     * same row, column or block. Else, this method may be extremely slow.
     * @param grid the sudoku grid
     * @return information about the number of solutions
     */
    public int getCountSolutions(Grid grid, int maxNrOfIterations) throws InterruptedException {
    	long l = System.currentTimeMillis();
    	this.maxNrOfIterations = maxNrOfIterations;
    	maxNrOfSolutions = 2;
    	nrOfIterations = 0;
    	nrOfSolutions = 0;
    	theUnsolvedGrid = grid;
    	theSolvedGrid = null;

    	grid.rebuildPotentialValues();
    	SolverGrid solverGrid = new SolverGrid(grid);
    	solve(solverGrid, null);
    	
    	if (OUTPUT) System.out.println("getCountSolutions(Grid) took " + (System.currentTimeMillis()-l)/1000f + " seconds"); //$NON-NLS-1$ //$NON-NLS-2$
    	if (OUTPUT) System.out.println("getCountSolutions(Grid) found " + nrOfSolutions + " solutions"); //$NON-NLS-1$ //$NON-NLS-2$
    	if (OUTPUT) System.out.println("nrOfIterations: " + nrOfIterations); //$NON-NLS-1$
        return nrOfSolutions;
    }

    @Override
	public String getProducerName() {
		return null;
	}
    
    // ****************************************** Private Methods *******************************************

    /**
     * This method is called if a solution has been found
     * @param solution The solution. If you want to keep the solution, use solution.clone() or return true (see below)
     * @return True if the solver should stop looking for more solution, if False the solver will look for more solutions.
     */
    private boolean onSolutionFound(SolverGrid solution) {
    	if (OUTPUT) System.out.println("Found solution #" + (nrOfSolutions+1) + " in " + nrOfIterations + " iterations"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
    	if (OUTPUT) System.out.println(solution.toString());

    	if (++nrOfSolutions==1) {
        	theSolvedGrid = new Grid(theUnsolvedGrid);
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                	theSolvedGrid.setCellValue(x, y, solution.getValue(x, y), theUnsolvedGrid.getCell(x, y).isGiven());
                }
            }
    	}
    	
    	return (nrOfSolutions>=maxNrOfSolutions);
    }

    /**
     * Try to solve the puzzle.
     * @throws InterruptedException 
     */
    private boolean solve(SolverGrid solverGrid, Random rand) throws InterruptedException {
    	
    	// someone wants us to cancel the operation
        if (Thread.interrupted()) throw new InterruptedException();
        
        // if maximum nr of iterations reached then stop the process
    	nrOfIterations++;
    	if (nrOfIterations>maxNrOfIterations) return false;

    	// (0) eliminate hidden singles first
    	solverGrid.check4HiddenSingles();
    	
    	// (1) if puzzle is invalid we're done
    	if (!solverGrid.isValid()) return false;
    	
    	// (2) if puzzle is solved we're done
    	if (solverGrid.isSolved()) return onSolutionFound(solverGrid);

    	// (3) find first empty cell
        int pos=0;
        for (; pos<81; pos++) {
            if (solverGrid.isEmpty(pos)) {
               	break;
            }
        }
        
        // (4) try each possible value for the cell
        BitSet candidates = (BitSet) solverGrid.getCandidates(pos).clone();
        int value = (rand==null) ? 1 : rand.nextInt(9)+1;
        for (int i=1; i<=9; i++) {
        	if (++value==10) value=1;
        	if (candidates.get(value)) {
                SolverGrid savedGrid = solverGrid.clone();
            	if (solverGrid.setValue(pos, value)) {
                	if (solve(solverGrid, rand)) return true;
            	}
            	solverGrid.restore(savedGrid);
        	}
        }
        // This code starts with the first set value while the code above uses a random start value
        /*for (int value=candidates.nextSetBit(0); value>0; value=candidates.nextSetBit(value+1)) {
            SolverGrid savedGrid = solverGrid.clone();
        	solverGrid.setValue(pos, value);
        	if (solve(solverGrid, rand)) return true;
        	solverGrid.restore(savedGrid);
        }*/
        
        // no solution found
        return false;
    }

	// ****************************************** SolverGrid *******************************************

	class SolverGrid implements Cloneable {
    	// the 81 Sudoku values (1..9), 0=empty cell 
    	private int[] values;	// int is faster than short or byte

    	// the 81 candidates (bits 1..9 used)
    	private BitSet[] candidates;
    	
    	private boolean isValid;
    	private int nrOfSetValues;
    	
        private int[][] neighbors;
        private int[][] neighbors_rows;
        private int[][] neighbors_columns;
        private int[][] neighbors_blocks;

    	private SolverGrid(Grid grid) {
    		this.candidates = new BitSet[81];
    		this.isValid = true;
    		this.nrOfSetValues = 0;
    		this.neighbors = NeighborManager.getNeighbors(grid);
    		this.neighbors_rows = NeighborManager.neighbors_rows();
    		this.neighbors_columns = NeighborManager.neighbors_columns();
    		this.neighbors_blocks = NeighborManager.neighbors_blocks(grid.getBlockCodes());
    		this.values = new int[81];

    		// initialize values
        	for (int y=0; y<9; y++) {
            	for (int x=0; x<9; x++) {
            		Cell cell = grid.getCell(x, y);
            		if (!cell.isEmpty()) setValue(x, y, cell.getValue());
            	}
        	}
    	}

    	/**
    	 * Use this constructor only in the clone method
    	 */
    	private SolverGrid() {}

    	@Override
    	public SolverGrid clone() {
    		SolverGrid clone = new SolverGrid();
    		clone.values = this.values.clone();
    		int counter = 0;
    		clone.candidates = new BitSet[81];
    		for (BitSet tmp:this.candidates) {
    			clone.candidates[counter++] = (tmp==null) ? null : (BitSet) tmp.clone();
    		}
    		clone.isValid = this.isValid;
    		clone.nrOfSetValues = this.nrOfSetValues;
    		clone.neighbors = this.neighbors;
    		clone.neighbors_rows = this.neighbors_rows;
    		clone.neighbors_columns = this.neighbors_columns;
    		clone.neighbors_blocks = this.neighbors_blocks;
    		return clone;
    	}

    	private void restore(SolverGrid other) {
    		this.values = other.values.clone();
    		int counter = 0;
    		for (BitSet tmp:other.candidates) {
    			this.candidates[counter++] = (tmp==null) ? null : (BitSet) tmp.clone();
    		}
    		this.isValid = other.isValid;
    		this.nrOfSetValues = other.nrOfSetValues;
    	}

    	/**
    	 * Sets the value at a certain position
    	 * @param x x-coordinate of the value to set (0..8)
    	 * @param y y-coordinate of the value to set (0..8)
    	 * @param value the value to set (1..9)
    	 */
    	private void setValue(int x, int y, int value) {
    		setValue(getPos(x, y), value);
    	}
    	
    	/**
    	 * Sets the value at a certain position
    	 * @param pos position of the value in the values array (0..80)
    	 * @param value the value to set (1..9)
    	 */
    	private boolean setValue(int pos, int value) {
    		// set new value
    		if (values[pos]==0 && value>0) nrOfSetValues++;
    		values[pos] = value;
			BitSet candidates = getCandidates(pos);
			candidates.clear();
    		
    		// remove the candidate in neighboring cells (row, column, block)
    		for (int m:neighbors[pos]) {
    			removeCandidates(m, value);
    		}
    		return isValid();
    	}
    	private void removeCandidates(int pos, int value) {
			if (isEmpty(pos)) {
    			BitSet candidates = getCandidates(pos);
    			candidates.clear(value);
    			int card = candidates.cardinality();
    			if (card==0) {
    				// no candidates left --> invalid
    				isValid=false;
    				return;
    			}
    			if (card==1) {
    				// naked single
    				setValue(pos, candidates.nextSetBit(0));
    			}
			}
			else if (values[pos]==value) {
				// if one of the neighboring cells is set to value
				// then the puzzle isn't valid
				isValid=false;
			}
    	}

    	/**
    	 * Get the value of a certain position
    	 * @param x x-coordinate of the value to set (0..8)
    	 * @param y y-coordinate of the value to set (0..8)
    	 * @return the value (1..9)
    	 */
    	private int getValue(int x, int y) {
    		return values[getPos(x, y)];
    	}

    	private void check4HiddenSingles() {
    		for (int pos=0; pos<81; pos++) {
    			if (isEmpty(pos)) {
    				BitSet candidates = getCandidates(pos);
    	            for (int value=candidates.nextSetBit(0); value>0; value=candidates.nextSetBit(value+1)) {
    	            	// check for hidden singles in rows
    	            	boolean hiddenSingleRow = true;
    	        		for (int r:neighbors_rows[pos]) {
    	        			if (isEmpty(r) && getCandidates(r).get(value)) {
    	        				hiddenSingleRow = false;
    	        				break;
    	        			}
    	        		}
    	        		if (hiddenSingleRow) {
    	        			setValue(pos, value);
    	        			check4HiddenSingles();
    	        			return;
    	        		}
    	        		else {
        	            	// check for hidden singles in columns
        	            	boolean hiddenSingleColumn = true;
        	        		for (int c:neighbors_columns[pos]) {
        	        			if (isEmpty(c) && getCandidates(c).get(value)) {
        	        				hiddenSingleColumn = false;
        	        				break;
        	        			}
        	        		}
        	        		if (hiddenSingleColumn) {
        	        			setValue(pos, value);
        	        			check4HiddenSingles();
        	        			return;
        	        		}
        	        		else {
            	            	// check for hidden singles in blocks
            	            	boolean hiddenSingleBlock = true;
            	        		for (int b:neighbors_blocks[pos]) {
            	        			if (isEmpty(b) && getCandidates(b).get(value)) {
            	        				hiddenSingleBlock = false;
            	        				break;
            	        			}
            	        		}
            	        		if (hiddenSingleBlock) {
            	        			setValue(pos, value);
            	        			check4HiddenSingles();
            	        			return;
            	        		}
        	        		}
    	        		}
    	            }
    			}
    		}
    	}
    	
    	private boolean isEmpty(int pos) {
    		return (values[pos]==0); 
    	}

    	private boolean isSolved() {
    		return isFull() && isValid(); 
    	}

    	private boolean isValid() {
    		return isValid; 
    	}

    	private boolean isFull() {
    		return (nrOfSetValues==81); 
    	}

    	/**
    	 * Return the candidates as BitSet
    	 * @return The candidates as BitSet.
    	 */
    	private BitSet getCandidates(int pos) {
    		if (candidates[pos]==null) {
    			candidates[pos] = new BitSet();
    			candidates[pos].set(1, 10);
    		}
    		return candidates[pos];
    	}
    	
    	private int getPos(int x, int y) {
    		return y*9 + x;
    	}
    	
        /**
         * Get a string representation of this grid.
         * For debugging purpose only.
         */
    	@Override
        public String toString() {
            StringBuilder result = new StringBuilder();
            result.append("isValid: " + isValid() + "\n\n"); //$NON-NLS-1$ //$NON-NLS-2$
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    int value = values[getPos(x, y)];
                    result.append((value>=1&&value<=9) ? ""+value : "."); //$NON-NLS-1$ //$NON-NLS-2$
                }
                result.append('\n');
            }
            result.append('\n');
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    BitSet cand = getCandidates(getPos(x, y));
                    StringBuffer s = new StringBuffer("---------"); //$NON-NLS-1$
                    for (int i=cand.nextSetBit(0); i>0; i=cand.nextSetBit(i+1)) {
                    	s.setCharAt(i-1, (char) (i+48));
                    }
                    result.append(s+((x<8)?"|":"")); //$NON-NLS-1$ //$NON-NLS-2$
                }
                result.append('\n');
            }
            return result.toString();
        }
    }
    
}